{-
	Bounded Search Tree Module
	
	r51
	
	29 March 2010
	
	Daniel De Guzman
	
	This module is part of the FPT Algorithm Implementation Project for the Massey University
	paper: 159.402 Programming Languages. It contains functions that primarily deal with
	the Depth Bound Search Tree Phase.
	
	In order to find the vertex cover, the following rules must be followed:
		Rule #1 If there is a vertex of degree 1, add its neighbour to the vertex cover
		Rule #2 If there is a vertex of degree 2, either
					a. Both neighbours are added to the vertex cover, or
					b. the vertex and its neighbours' neighbours are added to the vertex cover.
		Rule #3 If there is a vertex of degree 3, either
					a. the vertex is added to the cover, or
					b. the neighbours are added to the cover.
						
	Similar to the kernelization algorithm, this process is applied to the graph exhaustively. 
	And for each iteration, the graph is kernelized again.
		
-}

module BoundedSearchTree where

import Graph
import Kernelization
import Datatypes

-- |=========================================================================================|
-- |								 Bound Search Functions								 |
-- |=========================================================================================|

-- Main Function of the bound search algorithm
--	Checks for each rule and processes them accordingly
--	Does not do anything if criteria is not met
boundSearch :: ProcessGraph -> VertexCover
boundSearch (k, [], graph, vertexCover)
	| (read k==0) && ((length graph) == 0) 	= vertexCover
	| otherwise 							= []
boundSearch (k, (x:xs), graph, vertexCover)
	= 	if isSearchRuleOne x then 
			boundSearch $ toProcessGraph $ kernelize $ processSearchRuleOne (k, (x:xs), graph, vertexCover)
		else if isSearchRuleTwo x then 
			if isRuleTwoFirstChildNotEmpty then
				boundSearch $ toProcessGraph $ kernelize $ processSearchRuleTwoFC (k, (x:xs), graph, vertexCover)
				else if isRuleTwoSecondChildNotEmpty then 
				boundSearch $ toProcessGraph $ kernelize $ processSearchRuleTwoSC (k, (x:xs), graph, vertexCover)
				else boundSearch (k, xs, graph, vertexCover)
		else if isSearchRuleThree x then 
			if isRuleThreeFirstChildNotEmpty then 
				boundSearch $ toProcessGraph $ kernelize $ processSearchRuleThreeFC (k, (x:xs), graph, vertexCover)
			else if isRuleThreeSecondChildNotEmpty then
				boundSearch $ toProcessGraph $ kernelize $ processSearchRuleThreeSC (k, (x:xs), graph, vertexCover)
			else boundSearch (k, xs, graph, vertexCover)
		else boundSearch (k, xs, graph, vertexCover)
			where
				isRuleTwoFirstChildNotEmpty = ((boundSearch $ toProcessGraph $ kernelize $ processSearchRuleTwoFC (k, (x:xs), graph, vertexCover)) /= [])
				isRuleTwoSecondChildNotEmpty = ((boundSearch $ toProcessGraph $ kernelize $ processSearchRuleTwoSC (k, (x:xs), graph, vertexCover)) /= [])
				isRuleThreeFirstChildNotEmpty = ((boundSearch $ toProcessGraph $ kernelize $ processSearchRuleThreeFC (k, (x:xs), graph, vertexCover)) /= [])
				isRuleThreeSecondChildNotEmpty = ((boundSearch $ toProcessGraph $ kernelize $ processSearchRuleThreeSC (k, (x:xs), graph, vertexCover)) /= [])

-- Processes a graph according to the first rule:
--	Decrements K when vertex is added to the vertex cover
--	Removes vertex of degree 1 from the graph
--	Adds neighbour to the cover
--	Removes all occurrences of vertex added into the cover from the graph
processSearchRuleOne :: ProcessGraph -> ProcessGraph
processSearchRuleOne (k, (x:xs), graph, vertexCover)
	= 	(decrementIfNotInCover, xs, removeAllOccurrences, addNeighbourToCover)
			where
				decrementIfNotInCover = decrementK k (head (getNeighbours x)) vertexCover
				removeAllOccurrences = removeFromNeighboursList (head (getNeighbours x)) removeNeighbourFromVList
				removeNeighbourFromVList = removeVertex (head (getNeighbours x),[]) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addNeighbourToCover = addToCover (head (getNeighbours x)) vertexCover

-- Processes a graph according to the first rule:
--	First Child Edition
--		Add the neighbours to the vertex cover
--		Remove the vertex(x) from the graph
--		Remove the neighbours from the graph
--		Remove all occurrences of the neighbours from the neighbours' list
--		Decrement k each time a neighbour is added to the vertex cover
processSearchRuleTwoFC :: ProcessGraph -> ProcessGraph
processSearchRuleTwoFC (k, (x:xs), graph, vertexCover)
	= 	(decrementIfNotInCover, xs, removeAllOccurrences, addNeighboursToCover)
			where
				decrementIfNotInCover = decrementKs k (getNeighbours x) vertexCover
				removeAllOccurrences = removeFromManyNeighbours (getNeighbours x) removeNeighboursFromVList
				removeNeighboursFromVList = removeManyVertices (getNeighbours x) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addNeighboursToCover = addManyToCover (getNeighbours x) vertexCover

-- Process a graph according to the second rule:
--	Second Child Edition
--		Add vertex to cover
--		Add each of the vertex's neighbours' neighbours to the cover
--		Decrement K each time a new vertex is added to the cover
--		Remove vertex from the graph and necessary neighbours lists
--		Remove neighbour's neighbours from the graph and necessary neighbours list
processSearchRuleTwoSC :: ProcessGraph -> ProcessGraph
processSearchRuleTwoSC (k, (x:xs), graph, vertexCover)
	= 	(decrementIfNotInCover, (x:xs), removeAllOccurrences, addNeighboursToCover)
			where
				decrementIfNotInCover = decrementKsnb k (((getVertexLabel x):[]):(getManyNeighbours (getNeighbours x) removeVertexFromNeighbours)) vertexCover 
				removeAllOccurrences = removeManyVertices (getNeighbours x) removeNbsNbsFromVList
				removeNbsNbsFromVList = removeManyNeighbours (getManyNeighbours (getNeighbours x) removeVertexFromNeighbours) removeVertexFromNeighbours
				removeVertexFromNeighbours = removeFromNeighboursList (getVertexLabel x) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addNeighboursToCover = addManyNeighboursToCover (getManyNeighbours (getNeighbours x) (x:xs)) addVertexToCover
				addVertexToCover = addToCover (getVertexLabel x) vertexCover

-- Process a graph according to the third rule:
--	First Child Edition
--		Add vertex to cover
--		Remove vertex from graph
--		Remove all occurrences of vertex from neighbours' list
--		Decrement K if vertex is not in cover
processSearchRuleThreeFC :: ProcessGraph -> ProcessGraph
processSearchRuleThreeFC (k, (x:xs), graph, vertexCover)
	= 	(decrementIfNotInCover, xs, removeAllOccurrences, addVertexToCover)
			where
				decrementIfNotInCover = decrementK k (getVertexLabel x) vertexCover
				removeAllOccurrences = removeFromNeighboursList (getVertexLabel x) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addVertexToCover = addToCover (getVertexLabel x) vertexCover

-- Process a graph according to the third rule:
--	Second Child Edition
--		Add all of the vertex's neighbours to the cover
--		Remove each neighbour from the graph
--		Remove each neighbour from the neighbours' list
--		Decrement K if a vertex is added to cover
processSearchRuleThreeSC :: ProcessGraph -> ProcessGraph
processSearchRuleThreeSC (k, (x:xs), graph, vertexCover)
	= (decrementIfNotInCover, xs, removeAllOccurrences, addNeighboursToCover)
			where
				decrementIfNotInCover = decrementKs k (getNeighbours x) vertexCover
				removeAllOccurrences = removeFromManyNeighbours (getNeighbours x) removeNeighboursFromVList
				removeNeighboursFromVList = removeManyVertices (getNeighbours x) removeVertexFromGraph
				removeVertexFromGraph = removeVertex x graph
				addNeighboursToCover = addManyToCover (getNeighbours x) vertexCover
-- |-----------------------------------------------------------------------------------------|

-- |=========================================================================================|
-- |								Bound Search Subfunctions								 |
-- |=========================================================================================|

-- Adds a list of vertices to the vertex cover, if not already in there.
addManyToCover :: Neighbours -> VertexCover -> VertexCover
addManyToCover [] vc = vc
addManyToCover (x:xs) vc
	| elem x vc = addManyToCover xs vc
	| otherwise = addManyToCover xs (x:vc)

-- Adds a list of neighbours to the vertex cover, if not already there
addManyNeighboursToCover :: [Neighbours] -> VertexCover -> VertexCover
addManyNeighboursToCover [] vc = vc
addManyNeighboursToCover (x:xs) vc
	= addManyNeighboursToCover xs (addManyToCover x vc)

-- Decrements k if each vertex in the neighbour list is not in the cover
decrementKs :: K -> Neighbours -> VertexCover -> K
decrementKs k [] vertexCover = k
decrementKs k (x:xs) vertexCover
	| elem x vertexCover = decrementKs k xs vertexCover
	| otherwise 		 = decrementKs (show ((read k) - 1)) xs vertexCover

-- Decrements k if each vertex in the list of neighbours is not in the vertex cover
decrementKsnb :: K -> [Neighbours] -> VertexCover -> K
decrementKsnb k [] vertexCover = k
decrementKsnb k (x:xs) vertexCover
	= decrementKsnb (decKs k x) xs vertexCover
		where
			decKs :: K -> Neighbours -> K
			decKs k [] = k
			decKs k (x:xs)
				| elem x vertexCover = decKs k xs
				| otherwise 		 = decKs (show ((read k) - 1)) xs 

-- Finds all the neighbours of a list of vertices
getManyNeighbours :: [Vertex] -> Graph -> [Neighbours]
getManyNeighbours [] graph = []
getManyNeighbours (x:xs) graph
	= findNeighbours x graph : getManyNeighbours xs graph
		where
			-- Finds the  vertex's neighbours
			findNeighbours :: Vertex -> Graph -> Neighbours
			findNeighbours v [] = []
			findNeighbours v (x:xs)
				= 	if (v == getVertexLabel x)
					then getNeighbours x
					else findNeighbours v xs

-- Remove a list of vertices from all the neighbours
removeFromManyNeighbours :: [Vertex] -> Graph -> Graph
removeFromManyNeighbours [] graph = graph
removeFromManyNeighbours (x:xs) graph
	= removeFromManyNeighbours xs (removeFromNeighboursList x graph)

-- Removes a list of neighbours from a graph
removeManyNeighbours :: [Neighbours] -> Graph -> Graph
removeManyNeighbours [] graph = graph
removeManyNeighbours (x:xs) graph
	= removeManyNeighbours xs (removeManyVertices x graph)

-- Removes each vertex from a list of vertices
removeManyVertices :: Neighbours -> Graph -> Graph
removeManyVertices [] graph = graph
removeManyVertices (x:xs) graph
	= removeManyVertices xs (removeEachVertex x graph)
		where
			-- Removes a vertex at a time
			removeEachVertex :: Vertex -> Graph -> Graph
			removeEachVertex v [] = []
			removeEachVertex v (x:xs)
				= 	if (v == getVertexLabel x)
					then removeEachVertex v xs
					else x : removeEachVertex v xs

-- Turns a kgraph into a processgraph by duplicating the graph
toProcessGraph :: Kgraph -> ProcessGraph
toProcessGraph (k,g,vc) = (k,g,g,vc)
-- |-----------------------------------------------------------------------------------------|

-- |=========================================================================================|
-- |									Boolean Functions									 |
-- |=========================================================================================|

-- Checks if the graph entry fulfills the first rule
isSearchRuleOne :: GraphEntry -> Bool
isSearchRuleOne entry
	= if (length (getNeighbours entry) == 1)
		then True
		else False

-- Checks if the graph entry fulfills the second rule
isSearchRuleTwo :: GraphEntry -> Bool
isSearchRuleTwo entry
	= if (length (getNeighbours entry) == 2)
		then True
		else False

-- Checks if the graph entry fulfills the third rule
isSearchRuleThree :: GraphEntry -> Bool
isSearchRuleThree entry
	= if (length (getNeighbours entry) == 3)
		then True
		else False

-- |-----------------------------------------------------------------------------------------|
-- |=========================================================================================|